InforLorV4, Main, Exploration, bibRecord, 002727

Connectedness and Local Search for Bicriteria Knapsack Problems

Identifieur interne : 002727 ( Main/Exploration ); précédent : 002726; suivant : 002728

Connectedness and Local Search for Bicriteria Knapsack Problems

Auteurs : Arnaud Liefooghe [France] ; Luís Paquete [Portugal] ; Marco Sim Es [Portugal] ; José R. Figueira [France]

Source :

Lecture Notes in Computer Science [ 0302-9743 ]

RBID : ISTEX:E06DA8C2C11154A65313AF0DB584658B3D0ACD5D

Abstract

Abstract: This article reports an experimental study on a given structural property of connectedness of optimal solutions for two variants of the bicriteria knapsack problem. A local search algorithm that explores this property is then proposed and its performance is compared against exact algorithms in terms of running time and number of optimal solutions found. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact approaches.

Url:

DOI: 10.1007/978-3-642-20364-0_5

Affiliations:

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Connectedness and Local Search for Bicriteria Knapsack Problems</title>
<author><name sortKey="Liefooghe, Arnaud" sort="Liefooghe, Arnaud" uniqKey="Liefooghe A" first="Arnaud" last="Liefooghe">Arnaud Liefooghe</name>
</author>
<author><name sortKey="Paquete, Luis" sort="Paquete, Luis" uniqKey="Paquete L" first="Luís" last="Paquete">Luís Paquete</name>
</author>
<author><name sortKey="Sim Es, Marco" sort="Sim Es, Marco" uniqKey="Sim Es M" first="Marco" last="Sim Es">Marco Sim Es</name>
</author>
<author><name sortKey="Figueira, Jose R" sort="Figueira, Jose R" uniqKey="Figueira J" first="José R." last="Figueira">José R. Figueira</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:E06DA8C2C11154A65313AF0DB584658B3D0ACD5D</idno>
<date when="2011" year="2011">2011</date>
<idno type="doi">10.1007/978-3-642-20364-0_5</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-SFW4H26L-1/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">003551</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003551</idno>
<idno type="wicri:Area/Istex/Curation">003509</idno>
<idno type="wicri:Area/Istex/Checkpoint">000627</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000627</idno>
<idno type="wicri:doubleKey">0302-9743:2011:Liefooghe A:connectedness:and:local</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00575922</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00575922</idno>
<idno type="wicri:Area/Hal/Corpus">001838</idno>
<idno type="wicri:Area/Hal/Curation">001838</idno>
<idno type="wicri:Area/Hal/Checkpoint">001E64</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">001E64</idno>
<idno type="wicri:Area/Main/Merge">002769</idno>
<idno type="wicri:Area/Main/Curation">002727</idno>
<idno type="wicri:Area/Main/Exploration">002727</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Connectedness and Local Search for Bicriteria Knapsack Problems</title>
<author><name sortKey="Liefooghe, Arnaud" sort="Liefooghe, Arnaud" uniqKey="Liefooghe A" first="Arnaud" last="Liefooghe">Arnaud Liefooghe</name>
<affiliation wicri:level="4"><country xml:lang="fr">France</country>
<wicri:regionArea>LIFL – CNRS – INRIA Lille-Nord Europe, Université Lille 1</wicri:regionArea>
<placeName><settlement type="city">Lille</settlement>
<region type="region" nuts="2">Hauts-de-France</region>
<region type="old region" nuts="2">Nord-Pas-de-Calais</region>
</placeName>
<orgName type="university">Université Lille I - Sciences et technologies</orgName>
<orgName type="institution" wicri:auto="newGroup">Université Lille Nord de France</orgName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Paquete, Luis" sort="Paquete, Luis" uniqKey="Paquete L" first="Luís" last="Paquete">Luís Paquete</name>
<affiliation wicri:level="1"><country xml:lang="fr">Portugal</country>
<wicri:regionArea>CISUC, Department of Informatics Engineering, University of Coimbra</wicri:regionArea>
<wicri:noRegion>University of Coimbra</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Portugal</country>
</affiliation>
</author>
<author><name sortKey="Sim Es, Marco" sort="Sim Es, Marco" uniqKey="Sim Es M" first="Marco" last="Sim Es">Marco Sim Es</name>
<affiliation wicri:level="1"><country xml:lang="fr">Portugal</country>
<wicri:regionArea>CISUC, Department of Informatics Engineering, University of Coimbra</wicri:regionArea>
<wicri:noRegion>University of Coimbra</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Portugal</country>
</affiliation>
</author>
<author><name sortKey="Figueira, Jose R" sort="Figueira, Jose R" uniqKey="Figueira J" first="José R." last="Figueira">José R. Figueira</name>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>INPL, École des Mines de Nancy, Laboratoire LORIA</wicri:regionArea>
<wicri:noRegion>Laboratoire LORIA</wicri:noRegion>
<wicri:noRegion>Laboratoire LORIA</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: This article reports an experimental study on a given structural property of connectedness of optimal solutions for two variants of the bicriteria knapsack problem. A local search algorithm that explores this property is then proposed and its performance is compared against exact algorithms in terms of running time and number of optimal solutions found. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact approaches.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>Portugal</li>
</country>
<region><li>Hauts-de-France</li>
<li>Nord-Pas-de-Calais</li>
</region>
<settlement><li>Lille</li>
</settlement>
<orgName><li>Université Lille I - Sciences et technologies</li>
<li>Université Lille Nord de France</li>
</orgName>
</list>
<tree><country name="France"><region name="Hauts-de-France"><name sortKey="Liefooghe, Arnaud" sort="Liefooghe, Arnaud" uniqKey="Liefooghe A" first="Arnaud" last="Liefooghe">Arnaud Liefooghe</name>
</region>
<name sortKey="Figueira, Jose R" sort="Figueira, Jose R" uniqKey="Figueira J" first="José R." last="Figueira">José R. Figueira</name>
<name sortKey="Figueira, Jose R" sort="Figueira, Jose R" uniqKey="Figueira J" first="José R." last="Figueira">José R. Figueira</name>
<name sortKey="Liefooghe, Arnaud" sort="Liefooghe, Arnaud" uniqKey="Liefooghe A" first="Arnaud" last="Liefooghe">Arnaud Liefooghe</name>
</country>
<country name="Portugal"><noRegion><name sortKey="Paquete, Luis" sort="Paquete, Luis" uniqKey="Paquete L" first="Luís" last="Paquete">Luís Paquete</name>
</noRegion>
<name sortKey="Paquete, Luis" sort="Paquete, Luis" uniqKey="Paquete L" first="Luís" last="Paquete">Luís Paquete</name>
<name sortKey="Sim Es, Marco" sort="Sim Es, Marco" uniqKey="Sim Es M" first="Marco" last="Sim Es">Marco Sim Es</name>
<name sortKey="Sim Es, Marco" sort="Sim Es, Marco" uniqKey="Sim Es M" first="Marco" last="Sim Es">Marco Sim Es</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002727 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002727 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:E06DA8C2C11154A65313AF0DB584658B3D0ACD5D
   |texte=   Connectedness and Local Search for Bicriteria Knapsack Problems
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

Connectedness and Local Search for Bicriteria Knapsack Problems

Connectedness and Local Search for Bicriteria Knapsack Problems

Source :

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.